package com.xdja.linksort;

public class Main {

    public static void main(String[] args) {
        ListNode head = new ListNode(-1);
        ListNode l1 = new ListNode(5);
        ListNode l2 = new ListNode(3);
        ListNode l3 = new ListNode(4);
        ListNode l4 = new ListNode(0);

        head.next = l1;
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = null;

        ListNode temp = head;
        while (temp.next != null) {
            System.out.print(temp.val);
            temp = temp.next;
        }
        System.out.print(temp.val);
        System.out.println();

        mergeSort(head);

        temp = head;
        while (temp != null) {
            System.out.print(temp.val);
            temp = temp.next;
        }
    }

    /**
     * 单链表的归并排序
     */
    public  static ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //得到链表中间的数
        ListNode middle = getMiddle(head);
        ListNode sHalf = middle.next;
        //拆分链表
        middle.next = null;
        //递归调用
        return merge(mergeSort(head), mergeSort(sHalf));
    }

    /**
     * 拆分后的左边和右边进行排序,排序后进行合并
     *
     * @param leftNode  左半边
     * @param rightNode 右半边
     */
    public static ListNode merge(ListNode leftNode, ListNode rightNode) {
        ListNode headNode;
        ListNode currentNode;
        headNode = new ListNode(0);
        currentNode = headNode;
        while (leftNode != null && rightNode != null) {
            if (leftNode.val <= rightNode.val) {
                currentNode.next = leftNode;
                leftNode = leftNode.next;
            } else {
                currentNode.next = rightNode;
                rightNode = rightNode.next;
            }
            currentNode = currentNode.next;
        }
        currentNode.next = (leftNode == null) ? rightNode : leftNode;
        return headNode.next;
    }

    //找到中间点，然后分割
    public static ListNode getMiddle(ListNode head) {
        if (head == null) {
            return head;
        }
        //快慢指针
        ListNode slow;
        ListNode fast;
        slow = fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }
    }
}
